package first.codeTop.byteDance;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName Leetcode15
 * @description:
 * @author: 荣燊
 * @create: 2021-07-24 14:48
 **/
public class Leetcode15 {
    //  三数之和等于0
    public static void main(String[] args) {

    }

    public List<List<Integer>> threeSum(int[] nums) {
        // 1.先排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for (int k=0; k<nums.length-2; k++) {
            // 先固定一个数nums[k]
            if (nums[k] > 0) {
                break;
            }
            // 排除重复值
            if (k > 0 && nums[k] == nums[k-1]) {
                continue;
            }
            // 双指针维护一个滑动窗口
            int i = k+1;
            int j = nums.length-1;
            while (i < j) {
                int sum = nums[k]+nums[i]+nums[j];
                if (sum < 0) {
                    while (i<j && nums[i]==nums[++i]);
                } else if (sum > 0) {
                    while (i<j && nums[j]==nums[--j]);
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[k]);
                    list.add(nums[i]);
                    list.add(nums[j]);
                    res.add(list);
                    // 排除重复出现的数
                    while (i<j && nums[i]==nums[++i]);
                    while (i<j && nums[j]==nums[--j]);
                }
            }
        }
        return res;
    }
}
